package com.c2b.algorithm.leetcode.base;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * <a href='https://leetcode.cn/problems/find-if-path-exists-in-graph/'>寻找图中是否存在路径(Find if Path Exists in Graph)</a>
 * <p>有一个具有 n 个顶点的 双向 图，其中每个顶点标记从 0 到 n - 1（包含 0 和 n - 1）。图中的边用一个二维整数数组 edges 表示，其中 edges[i] = [ui, vi] 表示顶点 ui 和顶点 vi 之间的双向边。 每个顶点对由 最多一条 边连接，并且没有顶点存在与自身相连的边。</p>
 * <p>请你确定是否存在从顶点 source 开始，到顶点 destination 结束的 有效路径 。</p>
 * <p>给你数组 edges 和整数 n、source 和 destination，如果从 source 到 destination 存在 有效路径 ，则返回 true，否则返回 false 。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
 *      输出：true
 *      解释：存在由顶点 0 到顶点 2 的路径:
 *          - 0 → 1 → 2
 *          - 0 → 2
 *
 * 示例 2：
 *      输入：n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
 *      输出：false
 *      解释：不存在由顶点 0 到顶点 5 的路径.
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>3 <= n <= 10^5</li>
 *         <li>edges.length == n - 1</li>
 *         <li>edges[i].length == 2</li>
 *         <li>1 <= ui, vi <= n</li>
 *         <li>ui != vi</li>
 *         <li>题目数据给出的 edges 表示一个有效的星型图</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2024/3/5 9:43
 */
public class LC1971FindOfPathExistsInGraph_S {
    static class Solution {
        /**
         * 广度优先遍历
         */
        public boolean validPath(int n, int[][] edges, int source, int destination) {
            List<Integer>[] adj = new List[n];
            for (int i = 0; i < n; i++) {
                adj[i] = new ArrayList<Integer>();
            }
            for (int[] edge : edges) {
                int x = edge[0], y = edge[1];
                adj[x].add(y);
                adj[y].add(x);
            }
            boolean[] visited = new boolean[n];
            Queue<Integer> queue = new LinkedList<>();
            queue.offer(source);
            visited[source] = true;
            while (!queue.isEmpty()) {
                Integer vertex = queue.poll();
                if (vertex == destination) {
                    break;
                }
                for (Integer next : adj[vertex]) {
                    if (!visited[next]) {
                        queue.offer(next);
                        visited[next] = true;
                    }
                }
            }
            return visited[destination];
        }

        /**
         * 深度优先遍历
         */
        public boolean validPath2(int n, int[][] edges, int source, int destination) {
            List<Integer>[] adj = new List[n];
            for (int i = 0; i < adj.length; i++) {
                adj[i] = new ArrayList<>();
            }
            for (int[] edge : edges) {
                int x = edge[0];
                int y = edge[1];
                adj[x].add(y);
                adj[y].add(x);
            }
            boolean[] visited = new boolean[n];
            return dfs(source, destination, adj, visited);
        }

        private boolean dfs(int source, int destination, List<Integer>[] adj, boolean[] visited) {
            if (source == destination) {
                return true;
            }
            visited[source] = true;
            for (Integer next : adj[source]) {
                if (!visited[next] && dfs(next, destination, adj, visited)) {
                    return true;
                }
            }
            return false;
        }

        public boolean validPath3(int n, int[][] edges, int source, int destination) {
            if (source == destination) {
                return true;
            }
            UnionFind unionFind = new UnionFind(n);
            for (int[] edge : edges) {
                unionFind.union(edge[0], edge[1]);
            }
            return unionFind.connect(source, destination);
        }
    }

    static class UnionFind {
        /**
         * parent[x]：用来存放x在树形结构中的父节点(如果x是根节点，则令pre[x]=x)
         */
        private final int[] parent;
        /**
         *  路径压缩算法之二（加权标记法）
         */
        private final int[] rank;

        public UnionFind(int n) {
            this.parent = new int[n];
            this.rank = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            //
            /*
            加权标记法的核心在于对rank数组的逻辑控制，其主要的情况有：
            1、如果rank[x] < rank[y]，则令pre[x] = y；
            2、如果rank[x] == rank[y]，则可任意指定上级；
            3、如果rank[x] > rank[y]，则令pre[y] = x；
             */
            if (rootX != rootY) {
                // 如果 x的高度大于 y；则令y的上级为x
                if (rank[rootX] > rank[rootY]) {
                    parent[rootY] = rootX;
                } else {
                    // 如果x的高度和y的高度相同，则令y的高度+1
                    if (rank[rootX] == rank[rootY]) {
                        rank[rootY]++;
                    }
                    // 如果 x的高度小于 y；则令x的上级为y
                    // 如果 x的高度等于 y；则可任意指定上级，令x的上级为y
                    parent[rootX] = rootY;
                }
            }
        }

        private int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        public boolean connect(int x, int y) {
            return find(x) == find(y);
        }
    }
}
